package com.ywgt;

import java.util.Arrays;

public class FibonacciSearch {
    public static void main(String[] args) {
        int [] arr={1,2,3,4,5,6};
        System.out.println(getIndex(arr, 1));
    }


    /**
     * 获取斐波那契数列
     * @return
     */
    public static int[] fib(){
        int [] fib=new int[20];
        int tem=1;
        fib[0]=1;
        fib[1]=1;
        for (int i = 2; i < fib.length; i++) {
            fib[i]=fib[i-1]+fib[i-2];
        }
        return fib;
    }

    public static int getIndex(int [] arr,int val){
        int low=0;
        int high=arr.length-1;
        int k=0;
        int [] f=fib();
        int mid=0;
        while(high>f[k]-1){
            k++;
        }
        int [] temp=Arrays.copyOf(arr,f[k]);

        for (int i = high+1; i <temp.length ; i++) {
            temp[i]=arr[high];
        }
        while(low<=high){
            mid=low+f[k-1]-1;
            if(val<temp[mid]){
                high=mid-1;
                k--;
            }
            else if(val>temp[mid]){
                low=mid+1;
                k-=2;
            }else {
                if(high<mid){
                    return high;
                }else {
                    return mid;
                }
            }
        }
        return -1;
    }
}
